package class19;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class FindMinKth2 {
    public static int[] copyArray(int[] arr){
        int[] ans = new int[arr.length];
        for (int i=0;i!=ans.length;i++){
            ans[i] = arr[i];
        }
        return ans;
    }

    public static int minKth(int[] array,int k){
        int[] arr = copyArray(array);
        return process2(arr,0,arr.length-1,k-1);
    }

    public static void swap(int[] arr,int i1,int i2){
        int tmp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = tmp;
    }

    public static int[] partition(int[] arr,int L,int R,int pivot){
        int less = L -1;
        int more = R +1;
        int cur = L;
        while (cur <more){
            if (arr[cur] < pivot){
                swap(arr,++less,cur++);
            }else if (arr[cur] > pivot){
                swap(arr,cur,--more);
            }else {
                cur++;
            }
        }
        return new int[]{less+1,more-1};
    }

    public static int process2(int[] arr,int L,int R,int index){
        if (L==R){
            return arr[L];
        }
        int pivot = arr[L+(int)(Math.random()*(R-L+1))];
        int[] range = partition(arr,L,R,pivot);
        if (index >= range[0] && index <= range[1]){
            return arr[index];
        }else if (index < range[0]){
            return process2(arr,L,range[0]-1,index);
        }else {
            return process2(arr,range[1]+1,R,index);
        }
    }


    public static int minKth3(int[] array,int k){
        int[] arr = copyArray(array);
        return bfprt(arr,0,arr.length-1,k-1);
    }

    public static int bfprt(int[] arr,int L,int R,int index){
        if (L == R)
            return arr[L];
        int pivot = medianOfMedians(arr,L,R);
        int[] range = partition(arr,L,R,pivot);
        if (index >= range[0] && index <= range[1]){
            return arr[index];
        }else if (index < range[0]){
            return bfprt(arr,L,range[0]-1,index);
        }else {
            return bfprt(arr,range[1]+1,R,index);
        }
    }

    public static int medianOfMedians(int[] arr,int L,int R){
        int size = R - L +1;
        int offset = size % 5 == 0?0:1;
        int[] mArr = new int[size/5 + offset];

        for (int team = 0;team<mArr.length;team++){
            int teamFirst = L + team * 5;
            mArr[team] = getMedian(arr,teamFirst,Math.min(R,teamFirst+4));
        }
        return bfprt(mArr,0,mArr.length-1,mArr.length/2);
    }

    public static void insertionSort(int[] arr,int L,int R){
        for (int i=L+1;i<=R;i++){
            for (int j = i-1;j>=L&&arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
        }
    }

    public static int getMedian(int[] arr,int L,int R){
        insertionSort(arr,L,R);
        return arr[(L+R)/2];
    }

    public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr = new int[(int)(Math.random() * maxSize) + 1];
        for (int i= 0;i<arr.length;i++){
            arr[i] = (int)(Math.random()*(maxValue+1));
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("test begin!");
        for (int i=0;i<testTime;i++){
            int[] arr = generateRandomArray(maxSize,maxValue);
            int k = (int)(Math.random() * arr.length) + 1;
            int ans1 = minKth(arr,k);
            int ans2 = minKth3(arr,k);
            if (ans1 != ans2)
                System.out.println("Oops!");
        }
        System.out.println("test finish!");
    }
}
